package tree

import (
	"strconv"
)

//给定一个二叉树，返回所有从根节点到叶子节点的路径。
//说明: 叶子节点是指没有子节点的节点。

func BinaryTreePath(root *Node) (paths []string) {
	var constructPaths func(root *Node, path string)
	constructPaths = func(root *Node, path string) {
		if root != nil {
			pathSB := path
			pathSB += strconv.Itoa(root.Val)
			if root.Left == nil && root.Right == nil {
				paths = append(paths, pathSB)
			} else {
				pathSB += "->"
				constructPaths(root.Left, pathSB)
				constructPaths(root.Right, pathSB)
			}

		}
	}

	constructPaths(root, "")
	return
}

func BinaryTreePathBFS(root *Node) []string {
	paths := []string{}

	if root == nil {
		return paths
	}

	nodeQueue := []*Node{}
	pathQueue := []string{}

	nodeQueue = append(nodeQueue, root)
	pathQueue = append(pathQueue, strconv.Itoa(root.Val))

	for i := 0; i < len(nodeQueue); i++ {
		node, path := nodeQueue[i], pathQueue[i]

		if node.Left == nil && node.Right == nil {
			paths = append(paths, path)
			continue
		}

		if node.Left != nil {
			nodeQueue = append(nodeQueue, node.Left)
			pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Left.Val))
		}

		if node.Right != nil {
			nodeQueue = append(nodeQueue, node.Right)
			pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Right.Val))
		}

	}
	return paths
}
